﻿//1.小红的二叉树计数
//小红定义一个二叉树为“好二叉树”，当且仅当该二叉树所有节点的孩子数量为偶数（0或者2）。
//小红想知道，n个节点组成的好二叉树，共有多少种不同的形态？答案请对10^9+ 7取模。
//1≤n≤3000

#include <vector>
class Solution
{
public:
    int cntOfTrees(int n)
    {
        std::vector<long long> dp(n + 1);
        dp[0] = dp[1] = 1;
        for (int i = 3; i <= n; i += 2) {
            for (int left = 1; left < i; left += 2)
            {
                int right = i - 1 - left;
                dp[i] = (dp[i] + dp[left] * dp[right]) % 1000000007;
            }
        }
        return dp[n];
    }
};


//2.小红的可爱串
//小红定义一个字符串是可爱串，当且仅当该字符串包含子序列"red"，且不包含子串"red"。
//我们定义子序列为字符串中可以不连续的一段，而子串则必须连续。例如rderd包含子序列"red"，且不包含子串"red"，因此该字符串为可爱串。
//小红想知道，长度为n的、仅由'r'、'e'、'd'三种字母组成的字符串中，有多少是可爱串？答案请对10 ^ 9 + 7取模。
//数据范围：1≤n≤10^5
class Solution {
public:
    typedef long long ll;
    static const int N = 1e5 + 5, MOD = 1e9 + 7;
    ll f[N], g[N], h[N];

    // 快速幂
    ll ksm(ll x, ll n) {
        ll res = 1 % MOD;
        while (n) {
            if (n & 1)res = res * x % MOD;
            x = x * x % MOD;
            n >>= 1;
        }
        return res;
    }

    int kawaiiStrings(int n) {
        // f[i] = 长度为 i 的字符串中包含子串 red 的字符串的数量
        for (int i = 3; i <= n; i++)
            f[i] = (f[i - 1] * 3 + ksm(3, i - 3) - f[i - 3]) % MOD;
        // h[i] = 长度为 i 的字符串中不含子序列 red 但含子序列 re 的字符串的数量
        for (int i = 2; i <= n; i++)
            h[i] = (h[i - 1] * 2 + (i - 1) * ksm(2, i - 2)) % MOD;
        // g[i] = 长度为 i 的字符串中包含子序列 red 的字符串
        for (int i = 3; i <= n; i++)
            g[i] = (g[i - 1] * 3 + h[i - 1]) % MOD;
        return int((g[n] - f[n] + MOD) % MOD);
    }

};


//3.小红的元素乘积
//小红定义一个数为“完美数”，当且仅当该数仅有一个非零数字。例如 5000, 4, 1, 10, 200都是完美数。
//小红拿到了一个大小为n的数组，她希望选择两个元素，满足它们的乘积为完美数。
//小红想知道，共有多少种不同的取法？
//数据范围：1≤n≤2000 1≤a_i≤10^9


#include <string>
class Solution {
public:
    bool check(long long n)
    {
        if (n < 10) return true;
        string s;
        s = to_string(n);
        for (int i = 1; i < s.size(); i++)
        {
            if (s[i] != '0')   return false;
        }
        return true;
    }

    int perfectPair(vector<int>& arr)
    {
        int n = arr.size();
        int ans = 0;
        if (n < 2)  return 0;
        for (int i = 0; i < n; i++)
        {
            for (int j = i + 1; j < n; j++)
            {
                if (check((long long)arr[i] * arr[j]))  ans++;
            }
        }
        return ans;
    }
};